9808. Topological Sorting

 

Sandro is a well organised person. Every day he makes a list of things which need to be done and enumerates them from 1 to n. However, some things need to be done before others. In this task you have to find out whether Sandro can solve all his duties and if so, print the correct order.

 

Input. In the first line you are given an integer n and m (1 ≤ n ≤ 10000, 1 ≤ m ≤ 1000000). On the next m lines there are two distinct integers x and y, (1 ≤ x, y ≤ 10000) describing that job x needs to be done before job y.

 

Output. Print "Sandro fails." if Sandro cannot complete all his duties on the list. If there is a solution print the correct ordering, the jobs to be done separated by a whitespace. If there are multiple solutions print the one, whose first number is smallest, if there are still multiple solutions, print the one whose second number is smallest, and so on.

 

Sample input 1

Sample output 1

8 9

1 4

1 2

4 2

4 3

3 2

5 2

3 5

8 2

8 6

1 4 3 5 7 8 2 6

 

 

Sample input 2

Sample output 2

2 2

1 2

2 1

Sandro fails.

 

 

РЕШЕНИЕ

графы – топологическая сортировка

 

Анализ алгоритма

В задаче требуется найти лексикографически наименьшую топологическую сортировку. Воспользуемся алгоритмом Кана (Kahn). Вместо классической очереди воспользуемся очередью с приоритетами или множеством.

Изначально занесем в очередь вершины, в которые не входят ребра (из которых может начинаться топологическая сортировка). На каждой итерации будет извлекать из очереди наименьший элемент – так мы обеспечим построение лексикографически наименьшей топологической сортировки.

 

Реализация алгоритма

 

#include <cstdio>

#include <set>

#include <vector>

using namespace std;

 

vector<vector<int> > graph;

vector<int> InDegree, Order;

set<int> minHeap;

int i, n, m, a, b, v, to;

 

int main(void)

{

  scanf("%d %d",&n,&m);

  graph.assign(n+1,vector<int>());

  InDegree.assign(n+1,0);

 

  for(i = 0; i < m; i++)

  {

    scanf("%d %d",&a,&b);

    graph[a].push_back(b);

    InDegree[b]++;

  }

 

  for(i = 1; i < InDegree.size(); i++)

    if (InDegree[i] == 0) minHeap.insert(i);

 

  while(!minHeap.empty())

  {

    v = *minHeap.begin();

    minHeap.erase(minHeap.begin());

    Order.push_back(v);

 

    for(i = 0; i < graph[v].size(); i++)

    {

      to = graph[v][i];

      InDegree[to]--;

      if (InDegree[to] == 0) minHeap.insert(to);

    }

  }

 

  if (Order.size() < n)

    printf("Sandro fails."); 

  else

    for(i = 0; i < Order.size(); i++)

      printf("%d ",Order[i]); 

  printf("\n");

 

  return 0;

}